МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Інструкція до лабораторної роботи № 3 з курсу " Комп’ютерні методи дослідження інформаційних процесів та систем " для студентів спеціальності 6.1601 "Інформаційна безпека" Затверджено на засіданні кафедри «Захист інформації» Протокол № __ від __________ p. Львів – 2007 Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь: Інструкція до лабораторної роботи №3 з курсу " Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека " / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М. Іванюк - Львів: НУЛП, 2007.- 12 с. Укладачі: Леонід Васильович Мороз, к.т.н., доц. Зеновій Михайлович Стрілецький, к.т.н., доц. Віталій Миколайович Іванюк, асистент Відповідальний за випуск: І.Я. Тишик, ст.викл. Рецензент: В.В.Хома, д.т.н., проф.. В.М.Максимович, к.т.н., доц. Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь. Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші. Метод простої ітерації. Нехай дано лінійну систему
(1) Розглянемо матриці


Тоді систему (1) можна записати у вигляді матричного рівняння
(2) Будемо вважати, що діагональні коефіцієнти
(і = 1, 2,…, n). Розв’яжемо перше рівняння системи (1) відносно
, друге відносно
і т.д. Тоді одержимо еквівалентну систему
(3) де

, при
;
, при
;
;
;
Іноді кажуть, що система (3) зведена до нормального вигляду. Введемо матриці ( та (

Систему (3) запишемо у вигляді
(4) Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів
. Далі послідовно будуємо матриці-стовпці:
– перше наближення
– друге наближення і т.д. Будь-яке (k + 1)-е наближення обчислюється за формулою:
, (k = 0, 1, 2, …) (5) В розгорнутому вигляді
. Якщо послідовність наближень
має границю
, (6) то ця границя є розв’язком системи (3). На практиці ітераційний процес припиняють, коли
, де ( – гранична абсолютна похибка. Приклад. Розв’язати систему методом простої ітерації:
. Зведемо систему до нормального вигляду
(7) або в матричній формі
(8) За нульові наближення коренів системи приймаємо
. Підставляємо ці значення в праві частини рівняння (7). Одержимо перші наближення коренів
Далі знаходимо другі і треті наближення коренів

Умови збіжності ітераційного процесу Нехай задано зведена до нормального вигляду система лінійних рівнянь
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці α менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень. Для системи
або
, де
– сума модулів по стовпцях
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків. Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним. Для системи лінійних рівнянь, заданих у вигляді
, метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів
для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів). Приклад:
(9)
(10)
(11) Дещо простішій програмній реалізації піддається наступна формула методу простих ітерацій:
(13) Звідки вона береться? Відомо, що при зведенні системи
до вигляду
кожне
представляється у вигляді
або

. Якщо зняти обмеження j ( i, то цю формулу можна переписати у такому вигляді
. Звідси випливає, що
. Метод Зейделя Є система лінійних алгебраїчних рівнянь, що зведена до нормального вигляду
. Тоді за методом Зейделя, в...